home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Camelot / Camelot 078 (1990-06)(Swedish User Group of Amiga)(SE)(PD)[WB].zip / Camelot 078 (1990-06)(Swedish User Group of Amiga)(SE)(PD)[WB].adf / fassem / quick.a < prev    next >
Text File  |  1990-05-06  |  12KB  |  268 lines
  1.  
  2.  
  3. *************************************************************************
  4. *  This routine can be used to demostrate FASSEM.  To assemble, do:     *
  5. *                                                                       *
  6. *     fassem.demo quick.a -oquick.o          (For an object file)       *
  7. *     fassem.demo quick.a -oquick.o -lram:x  (For a listing)            *
  8. *     fassem.demo quick.a -oquick.o -cx      (For a cross reference)    *
  9. *     fassem.demo >ram:x quick.a -cx         (Cross ref to a file)      *
  10. *     fassem.demo quick.a -cn                (Kill the demo message)    *
  11. *     fassem.demo quick.a -dFASSEM           (Use IS and UNDEF code)    *
  12. *     fassem.demo quick.a -dERROR            (Show error from xdef)     *
  13. *                                                                       *
  14. *  The above options may be combined.                                   *
  15. *************************************************************************
  16.  
  17. *************************************************************************
  18. *     QUICKSORT ROUTINE (c) 1990 Edward Lappin, all rights reserved.    *
  19. *      From:  Sorting and Searching by Knuth, pages 116-117.            *
  20. *                                                                       *
  21. *  int sort(mainarray,tagarray,length)                                  *
  22. *        Sort the main array in order of lower to higher values.        *
  23. *     The tagarray is used to keep track of where the data was moved.   *
  24. *  Inputs:  mainarray - pointer to first index of the main data.  When  *
  25. *            (long *)   sorted, mainarray[0] will have the smallest     *
  26. *                       value and mainarray[length-1] will have the     *
  27. *                       largest value.  IMPORTANT:  the array MUST have *
  28. *                       two extra locations:  mainarray[-1] must exist  *
  29. *                       and mainarray[length] must exist.  These are    *
  30. *                       used to increase the efficiency of the algorithm*
  31. *           tagarray  - These are tags associated with the mainarray    *
  32. *            (long *)   data.  If the data in mainarray is swapped, the *
  33. *                       tag data is also swapped.  This allows identi-  *
  34. *                       fication of the data when sorted.               *
  35. *           length    - # of entries to sort.  Must be 1 to 65533.      *
  36. *  Outputs: sort      - # of swaps done (somewhat fudged).              *
  37. *************************************************************************
  38.  
  39. *************************************************************************
  40. *  The following variables are used internally:                         *
  41. *     a0    - ptr to start of the main array.                           *
  42. *     a1    - (tagarray-mainarray).  This is added into a pointer into  *
  43. *              the mainarray to get a location in tagarray.             *
  44. *     a2    - Scan ptr i (into the mainarray).                          *
  45. *     a3    - Scan ptr j (into the mainarray).                          *
  46. *     a4    - Stack for the quicksort partitions left to do.  When this *
  47. *              equals sp, the stack is empty.  We push the left boundary*
  48. *              first, then the right.  Both are ptrs into mainarray.    *
  49. *     a5    - Left boundary of current working partition (mainarray ptr)*
  50. *     d0    - Current compare value.                                    *
  51. *     d1    - Swap value location.                                      *
  52. *     d2    - Compare location.                                         *
  53. *     d3    - Right boundary of current partition (mainarray ptr).      *
  54. *     d4    - Smallest size to do quicksort partition on (mult by size) *
  55. *     d5    - Swap counter.                                             *
  56. *************************************************************************
  57.  
  58. SMALLINT    equ      $80000000      Min and max compare values
  59. LARGEINT    equ      $7FFFFFFF
  60.  
  61. SMALLLIMIT  equ      9              Min partition size for sort
  62. thesize     equ      4              Bytes for key or tag element
  63.  
  64. multtag     macro                   Parameter is reg to mult by tagsize
  65.             ifne     thesize-4
  66.              fail    <tag size does not match code>
  67.              endc
  68.             add.l    \1,\1
  69.             add.l    \1,\1
  70.             endm
  71. *
  72. *  The following are defined first using equ and reg
  73. *
  74. saveregsp   equ      8*4            Bytes used on stack to save registers
  75. saveregs    reg      a2-a5/d2-d5
  76.  
  77. mainarray   equ      saveregsp+4
  78. tagarray    equ      saveregsp+8
  79. length      equ      saveregsp+12
  80. *
  81. *  The IS directive can be used with FASSEM to assign any text.  To reuse
  82. *the symbol names, it is necessary to undefine them.
  83. *
  84.             ifd      FASSEM
  85.  
  86.             undef    saveregsp,saveregs,mainarray,tagarray,length
  87.  
  88. saveregsp   is       8*4            Bytes used on stack to save registers
  89. saveregs    is       a2-a5/d2-d5
  90.  
  91. mainarray   is       saveregsp+4
  92. tagarray    is       saveregsp+8
  93. length      is       saveregsp+12
  94.             endc
  95.  
  96. _sort       equ      *
  97.             movem.l  saveregs,-(sp)
  98.             moveq    #0,d5
  99.             move.l   mainarray(sp),a0
  100.             move.l   tagarray(sp),a1
  101.             suba.l   a0,a1                Want tag-main in a1
  102.             moveq    #SMALLLIMIT*thesize,d4
  103. *
  104. *  Check to see if we have enough elements to quicksort and set initial
  105. *partition. 
  106. *
  107. Q1          move.l   length(sp),d1
  108.             multtag  d1                Convert length to offset bytes
  109.             move.l   #SMALLINT,-thesize(a0)  Set limit markers
  110.             move.l   #LARGEINT,0(a0,d1.l)
  111.             cmp.l    d4,d1
  112.             bls      Q9                If not big enough, skip
  113.             move.l   sp,a4             Initialize partition stack
  114.             move.l   a0,a5             Set left limit
  115.             move.l   d1,d3
  116.             subq.l   #thesize,d3
  117.             add.l    a0,d3             Set right limit
  118. *
  119. *  Setup to check the partition from a5 (l) to d3 (r).  We will see if we
  120. *need to create a new partition or just swap.
  121. *
  122. Q2          lea      thesize(a5),a2    Set left to right scan (i) to l+1
  123.             move.l   d3,a3
  124.             addq.l   #thesize,a3       Set right to left scan (j) to r+1
  125.             move.l   (a5),d0           Set d0 (K) to mainarray[l]
  126. *
  127. *  Scan from left to right, then right to left.
  128. *
  129. Q3          cmp.l    (a2)+,d0
  130.             bgt      Q3
  131.             subq.l   #thesize,a2       Convert back to point to last compare
  132. Q4          cmp.l    -(a3),d0
  133.             blt      Q4
  134. Q5          cmp.l    a2,a3
  135.             bls.s    Q7                If j <= i, we will use the stack
  136. *
  137. *  This is the case of j > i after the scan.  We only need to swap the
  138. *locations of i and j.
  139. *
  140. Q6          move.l   0(a2,a1.l),d1
  141.             move.l   0(a3,a1.l),0(a2,a1.l)
  142.             move.l   d1,0(a3,a1.l)     The tags are swapped
  143.             move.l   (a2),d1
  144.             move.l   (a3),(a2)+        We want to increase i by 1
  145.             move.l   d1,(a3)           The mainarray keys are swapped
  146.             addq.l   #1,d5
  147.             bra      Q3
  148. *
  149. *  This is the case of j <= i after the scan.  We want to swap l and j.
  150. *Then, we need to determine if a partition needs to be split and put on the
  151. *stack.
  152. Q7          move.l   (a5),d1
  153.             move.l   (a3),(a5)
  154.             move.l   d1,(a3)           The mainarray keys are swapped
  155.             move.l   0(a5,a1.l),d1
  156.             move.l   0(a3,a1.l),0(a5,a1.l)
  157.             move.l   d1,0(a3,a1.l)     The tags are swapped
  158.             addq.l   #1,d5
  159.             move.l   d3,d1
  160.             sub.l    a3,d1             r-j
  161.             move.l   a3,d2
  162.             sub.l    a5,d2             j-l
  163.             cmp.l    d1,d2
  164.             bhi      chkother
  165. *
  166. *  This is the case of r-j >= j-l.  Check to see if j-l > M.  If so, we
  167. *will create a new partition and place on the stack.
  168. *
  169.             cmp.l    d4,d2
  170.             ble.s    smalljl
  171.             pea      thesize(a3)       j+1 - partition to do later
  172.             move.l   d3,-(sp)          r
  173.             move.l   a3,d3
  174.             subq.l   #thesize,d3       Set r = j-1
  175.             bra      Q2                Continue scan
  176. smalljl     cmp.l    d4,d1
  177.             ble.s    Q8
  178. *
  179. *  This is the case of r-j > M >= j-l.  We want to start a new scan.
  180. *
  181.             lea      4(a3),a5          Set l = j+1
  182.             bra      Q2
  183. *
  184. *  This is the case of j-l > r-j.  Check to see if r-j > M.  If so, new
  185. *partition.
  186. *
  187. chkother    cmp.l    d4,d1
  188.             ble.s    smallrj
  189.             move.l   a5,-(sp)          l    - partition to do later
  190.             pea      -thesize(a3)      j-1
  191.             lea      thesize(a3),a5    Set l = j+1
  192.             bra      Q2                Continue scan
  193. smallrj     cmp.l    d4,d2
  194.             ble.s    Q8
  195. *
  196. *  This is the case of j-l > M >= r-j.  We want to start a new scan.
  197. *
  198.             move.l   a3,d3
  199.             subq.l   #thesize,d3       Set r = j-1
  200.             bra      Q2
  201. *
  202. *  We are done with the current partition.  See if there are any on the
  203. *stack.  If so, use the top one.  If not, we are done with partitioning.
  204. *
  205. Q8          cmp.l    a4,sp             Check cc (same as High or Same)
  206.             bcc      Q9                We are done since empty stack
  207.             move.l   (sp)+,d3          Get r from stack
  208.             move.l   (sp)+,a5          Get l from stack
  209.             bra      Q2                Start the new scan
  210. *
  211. *  At this point, we need to do an insertion sort to finish up the data.
  212. *For partitions smaller than the cutoff size, the data is not sorted.  This
  213. *will sort the data within each partition.
  214. *
  215. Q9          move.l   length(sp),d4     Get the length
  216.             subq.l   #1,d4
  217.             ble.s    done              If 0 or 1 elements, done
  218.             move.l   a0,a3             Set j to first element
  219.             move.l   (a3)+,d1
  220. insertloop  move.l   (a3)+,d2          We have j in d2 and j-1 in d1
  221.             cmp.l    d1,d2
  222.             blt.s    fix1
  223. fix1ok      subq.l   #1,d4
  224.             beq.s    done
  225.             move.l   (a3)+,d1          Get next element
  226.             cmp.l    d2,d1
  227.             blt.s    fix2
  228. fix2ok      subq.l   #1,d4
  229.             bne.s    insertloop
  230. done        move.l   d5,d0
  231.             movem.l  (sp)+,saveregs
  232.             rts
  233. *
  234. *  Fix the section around j.
  235. *     At the start, d2 = [j], d1 = [j-1], a3 = j+1
  236. *
  237. fix1        move.l   -thesize(a3,a1),d0      d0 = R[j]
  238.             lea      -thesize*2(a3),a2       a2 = i = j-1
  239. fix1loop    move.l   (a2),thesize(a2)        K[i] -> K[i+1]
  240.             move.l   0(a2,a1.l),thesize(a2,a1.l)  R[i] -> R[i+1]
  241.             cmp.l    -(a2),d2
  242.             blt      fix1loop                Continue until >= K[i]
  243.             move.l   d2,thesize(a2)          K[j] -> K[i+1]
  244.             move.l   d0,thesize(a2,a1.l)     R[j] -> R[i+1]
  245.             move.l   -thesize(a3),d2         Fix the new K[j]
  246.             addq.l   #1,d5
  247.             bra.s    fix1ok
  248. *
  249. *  Fix the section around j.  Like above except reverse d1 and d2
  250. *     At the start, d1 = [j], d2 = [j-1], a3 = j+1
  251. *
  252. fix2        move.l   -thesize(a3,a1),d0      d0 = R[j]
  253.             lea      -thesize*2(a3),a2       a2 = i = j-1
  254. fix2loop    move.l   (a2),thesize(a2)        K[i] -> K[i+1]
  255.             move.l   0(a2,a1.l),thesize(a2,a1.l)  R[i] -> R[i+1]
  256.             cmp.l    -(a2),d1
  257.             blt      fix2loop                Continue until >= K[i]
  258.             move.l   d1,thesize(a2)          K[j] -> K[i+1]
  259.             move.l   d0,thesize(a2,a1.l)     R[j] -> R[i+1]
  260.             move.l   -thesize(a3),d1         Fix the new K[j]
  261.             addq.l   #1,d5
  262.             bra.s    fix1ok
  263.  
  264.             ifd      ERROR
  265.              xdef    _sort
  266.             endc
  267.  
  268.